λ¬Έμ
π Logic
private void combination(int idx, int start, int keySize, HashSet<Integer> keys, int n, String[][] relation) {
if (idx == keySize) {
// μ΄λ―Έ λ½μ ν보ν€λΌλ©΄ μ μΈ(μ μΌμ±, μ΅μμ± κ²μ¬), keysμ keyκ° ν¬ν¨λλ€λ©΄ μ΅μμ± λ§μ‘± X
for (HashSet<Integer> key : candidateKeys)
if (keys.containsAll(key)) return;
// λ½μ ν보ν€μ μΈλ±μ€λ₯Ό νμΈνμ¬ μ μΌμ±μ νμΈν set
HashSet<String> spareKeys = new HashSet<>();
for (String[] rel : relation) {
StringBuilder sb = new StringBuilder();
// μ ν(keysμ μΆκ°)ν μμ± μ²΄ν¬
for (int k : keys)
sb.append(rel[k]);
spareKeys.add(sb.toString());
}
// mapμ ν¬κΈ°μ relationμ κΈΈμ΄κ° κ°λ€λ©΄ λͺ¨λ ννμ λν΄μ μ€λ³΅λ κ°μ΄ μλ€λ μλ―Έμ΄λ―λ‘ ν보ν€κ° λ μ μμ
if (spareKeys.size() == relation.length)
candidateKeys.add(keys);
} else {
for (int i = start; i < n; i++) {
HashSet<Integer> selectedKeys = new HashSet<>(keys);
selectedKeys.add(i);
combination(idx + 1, i + 1, keySize, selectedKeys, n, relation);
}
}
}
- ν보ν€λ₯Ό μμ±νλ ν¨μ
-
μ μΌμ±κ³Ό μ΅μμ±μ λ§μ‘±νλ ν보ν€λ₯Ό
candidateKeysμ μΆκ°νλ€.- λ§λ ν보ν€μ ν΄λΉνλ μμ±κ°μΌλ‘
Mapμ λ§λ€μμλ, μ€λ³΅μμ΄relationμλ§νΌ λ§λ€μ΄μ§λ€λ©΄ μ΄λ₯Ό λ§μ‘±νλ ν보ν€μ΄λ€.
- λ§λ ν보ν€μ ν΄λΉνλ μμ±κ°μΌλ‘
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
// ν보ν€λ€μ μ μ₯ν ArrayList
static ArrayList<HashSet<Integer>> candidateKeys = new ArrayList<>();
public int solution(String[][] relation) {
int n = relation[0].length;
// 1κ°λΆν° nκ°κΉμ§μ νλ³΄ν€ μμ± μλ
for (int i = 0; i < n; i++)
combination(0, 0, i + 1, new HashSet<>(), n, relation);
return candidateKeys.size();
}
private void combination(int idx, int start, int keySize, HashSet<Integer> keys, int n, String[][] relation) {
if (idx == keySize) {
// μ΄λ―Έ λ½μ ν보ν€λΌλ©΄ μ μΈ(μ μΌμ±, μ΅μμ± κ²μ¬), keysμ keyκ° ν¬ν¨λλ€λ©΄ μ΅μμ± λ§μ‘± X
for (HashSet<Integer> key : candidateKeys)
if (keys.containsAll(key)) return;
// λ½μ ν보ν€μ μΈλ±μ€λ₯Ό νμΈνμ¬ μ μΌμ±μ νμΈν set
HashSet<String> spareKeys = new HashSet<>();
for (String[] rel : relation) {
StringBuilder sb = new StringBuilder();
// μ ν(keysμ μΆκ°)ν μμ± μ²΄ν¬
for (int k : keys)
sb.append(rel[k]);
spareKeys.add(sb.toString());
}
// mapμ ν¬κΈ°μ relationμ κΈΈμ΄κ° κ°λ€λ©΄ λͺ¨λ ννμ λν΄μ μ€λ³΅λ κ°μ΄ μλ€λ μλ―Έμ΄λ―λ‘ ν보ν€κ° λ μ μμ
if (spareKeys.size() == relation.length)
candidateKeys.add(keys);
} else {
for (int i = start; i < n; i++) {
HashSet<Integer> selectedKeys = new HashSet<>(keys);
selectedKeys.add(i);
combination(idx + 1, i + 1, keySize, selectedKeys, n, relation);
}
}
}
}
βοΈ Review
- μ‘°ν©κ³Ό μ§ν©μ λν λ¬Έμ μμ λ°λ‘ λ μ¬λ¦΄ μ μμμ§λ§ "μ μΌμ±" κ³Ό "μ΅μμ±" μ λ§μ‘±νλ ν보ν€λ₯Ό ꡬννλλ°μμ λ§νλ€ ..